#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <cmath>
#include <cstring>

using namespace std;

class Solution
{
public:
    int minimumWhiteTiles(string floor, int numCarpets, int carpetLen)
    {
        // dp[i][c] = dp[i - 1][c]
        // dp[i][c] = dp[i - len][c - 1] + s[i+1] - s[i-len+1]
        int n = floor.size();
        if(numCarpets * carpetLen >= n){
            return 0;
        }
        vector<vector<int>> dp(n);
        for (int i = 0; i < n; ++i)
        {
            dp[i] = vector<int>(numCarpets + 1, 0);
        }
        vector<int> preSum(n + 1, 0);
        for (int i = 0; i < n; ++i)
        {
            preSum[i + 1] = preSum[i] + (floor[i] == '1');
        }
        int total = preSum[n];
        for (int c = 1; c <= numCarpets; ++c)
        {
            int minLeft = c * carpetLen;
            for (int i = 0; i < minLeft; ++i){
                dp[i][c] = preSum[i + 1];
            }
            for (int i = minLeft; i < n; ++i)
            {
                dp[i][c] = max(
                    dp[i - 1][c],
                    dp[i - carpetLen][c - 1] + preSum[i + 1] - preSum[i - carpetLen + 1]);
            }
        }
        return total - dp[n-1][numCarpets];
    }
};
